Computerized rendering of a scene involves simulating the interaction of light with objects in the scene. Ray tracing is a well studied technique that involves tracing the path of light as it bounces around the scene. A challenge with ray tracing is determining which parts of a scene are hit by a given ray of light. In order to render a scene with sufficient quality, the process can require tracing millions of rays through the scene. Objects in a scene are generally represented by triangles, although any suitable geometric shape can be used. Tracing a ray through a scene involves testing the ray for intersection with each triangle.
Scenes can easily contain many thousands of triangles, leading to many billions of ray/triangle intersection tests, which can quickly become impractical. It is generally accepted that calculating intersections between rays and triangles is the most computationally expensive aspect of the ray tracing method. Acceleration structures have been developed to reduce the number of ray/triangle intersections tests, and thus accelerate the image rendering process. The idea behind acceleration structures is to help decide as quickly as possible which triangles in a scene that a particular ray is likely to intersect and to reject the large majority of the triangles which the ray will never hit.
One type of acceleration structure is called the bounding volume hierarchy (BVH). The BVH is a hierarchical structure that partitions the objects in a scene. For example, where the objects are represented by triangles, a bounding volume may enclose all or portions of some triangles in the scene. Bounding volumes can be any suitable shape (e.g., sphere, cylinder, etc.), but are typically cubes (six square faces) or cuboids (six rectangular faces) and thus are commonly referred to as bounding boxes. The motivation behind bounding volumes is that performing an intersection test with a bounding volume is usually cheaper than performing the test with each triangle (or other geometry) enclosed by the bounding volume.
A BVH defines a tree comprising a root node corresponding to a bounding volume that contains all other bounding volumes, and hence all the triangles that comprise the scene. In other words, the bounding volume at the root node represents the entire scene. Each node in the tree has a number of children that are either internal nodes that contain further bounding volumes (e.g., a sub tree of bounding volumes) or are leaf nodes.
Building efficient acceleration structures for random spatial data (e.g., triangles) is an ever evolving and much published topic. Top-down and bottom-up builders have been researched with each having advantages and disadvantages. Top-down organizations work well with data sets that are too large to fit on-chip, while a bottom-up organization works well with data sets that can fit on-chip. As data sets continually grow in size, new hardware algorithms are required for organizing data structures that are too large to be stored on-chip. This and other issues are addressed by embodiments of the present disclosure, individually and collectively.